﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0200_ConstructArray : IAlgorithm
    {
        // 667. 优美的排列 II

        /*
        给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

        假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
        返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。

        提示：
            1 <= k < n <= 10^4
        */

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            foreach (var item in ConstructArray(4, 1))
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        public int[] ConstructArray(int n, int k)
        {
            var res = new int[n];
            res[0] = 1;
            var preorder = true;
            int l = 2, r = n;
            for (int i = 1; i < n; i++)
            {
                if (k > 1)
                {
                    k--;
                    preorder = !preorder;
                }
                if(preorder)
                    res[i] = l++;
                else
                    res[i] = r--;
            }
            return res;
        }
    }
}
